package leedcode_path.treeNoDE;

public class 修建二叉搜索树 {
    /*
    * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。
    * 修剪树 不应该 改变保留在树中的元素的相对结构
    * (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
    *
    * 这题我感觉跟上一题的删除二叉树的节点很像啊
    * 不同就是这个有范围，要想想这么接节点，他不是删一个，是删很多，所以要全部都遍历一遍，，ok
    *
    *
    * 注意本题用前序不可以，因为根节点删完之后就退出循环了
    * 用中序和后序应该都可以‘
    * *
     */

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root==null) return null;
        root.left=trimBST(root.left,low,high);
        root.right = trimBST(root.right, low, high);
        if (root.val<low||root.val>high){
            if (root.left==null&&root.right==null){
                return null;
            }else if (root.left==null&&root.right!=null){
                return root.right;
            }else if (root.left!=null&&root.right==null){
                return root.left;
            }else {
                TreeNode cur=root.right;
                while (cur.left!=null) cur=cur.left;
                cur.left=root.left;
                return root.right;
            }
        }

        return root;
    }

}
